package com.buddy.summary.code.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

public class BucketSort {
    private static double[] bucketSort(double[] arr) {
        //得到最大数组最大值和最小值,并计算差值
        double max = arr[0];
        double min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];

        }
        double d = max - min;
        //2.初始化桶
        int bucketNum = arr.length;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<>());
        }
        //3.遍历原始数组,将每个元素放入桶中
        for (int i = 0; i < arr.length; i++) {
            int num = (int) ((arr[i] - min) * (bucketNum - 1) / d);
            bucketList.get(num).add(arr[i]);
        }
        //4.对桶内进行排序
        for (int i = 0; i < bucketList.size(); i++) {
            Collections.sort(bucketList.get(i));
        }
        //输出全部元素
        double[] sortedArr = new double[arr.length];
        int index = 0;
        for (LinkedList<Double> list : bucketList) {
            for (double ele : list) {
                sortedArr[index] = ele;
                index++;
            }
        }
        return sortedArr;
    }

    public static void main(String[] args) {
        double[] arr = new double[]{
                4.12,6.421,0.0023,3.0,2.123,8.122,4.12,10.09
        };
        System.out.println(Arrays.toString(bucketSort(arr)));
    }
}
